package com.lili.dt;

import java.util.List;

/**
 * @Auther: 李 力
 * @Date: 2024/8/7
 * @Description: 01背包问题
 * @version: 1.0
 */
public class BaiBao01 {

        /*
        1. n个物品都是固体，有重量和价值
        2. 现在你要取走不超过 10克 的物品
        3. 每次可以不拿或全拿，问最高价值是多少

            编号 重量(g)  价值(元)                        简称
            1   4       1600           黄金一块   400    A
            2   8       2400           红宝石一粒 300    R
            3   5       30             白银一块         S
            0   1       1_000_000      钻石一粒          D
        1_001_630

        1_002_400
        贪心算法并不能得出最优解，要想得出最优解需要用动态规划
     */

    private static class Item {
        public int index;
        public String name;
        public int weight;
        public int value;

        public Item(int index, String name, int weight, int value) {
            this.index = index;
            this.name = name;
            this.weight = weight;
            this.value = value;
        }
    }

    public static int getMaxValue(List<Item> items, int total) {
        int[][] dp = new int[items.size()][total + 1];
        Item item = items.get(0);
        for (int j = 0; j < total + 1; j++) {
            if (j > item.weight) {
                dp[0][j] = item.value;
            } else {
                dp[0][j] = 0;
            }
        }
        for (int i = 1; i < dp.length; i++) {
            Item itemI = items.get(i);
            for (int j = 0; j < total + 1; j++) {
                if (j >= itemI.weight) {
                    dp[i][j] = Math.max(dp[i - 1][j], itemI.value + dp[i - 1][j - itemI.weight]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[dp.length - 1][total];
    }


    //降维
    public static int getMaxValue2(List<Item> items, int total) {
        int[] dp = new int[total + 1];
        Item item = items.get(0);
        for (int j = 0; j < total + 1; j++) {
            if (j > item.weight) {
                dp[j] = item.value;
            } else {
                dp[j] = 0;
            }
        }
        for (int i = 1; i < items.size(); i++) {
            Item itemI = items.get(i);
            for (int j = total; j > 0; j--) {
                if (j >= itemI.weight) {
                    dp[j] = Math.max(dp[j], itemI.value + dp[j - itemI.weight]);
                }
            }
        }
        return dp[total];
    }

}
